package priorityqueue;

import java.util.Arrays;

public class MyHeap {
    private int elem[];
    private int usedSize;
    private static final int DEFAULT_SIZE=11; // 注意：PriorityQueue源码中就是默认先开11个空间
    // 利用构造方法初始化
    public MyHeap() {
        elem = new int[DEFAULT_SIZE];
    }

    // 把灵活变动的数组放进堆数组中
    public void initMyHeap(int[] arr){
        for(int i = 0; i < arr.length; i++){
            elem[i] = arr[i];
            usedSize++;
        }
    }

    // 建堆
    public void createHeap(){
        for (int parent = (usedSize-1-1)/2; parent >= 0; parent--) {  // 注意：数组下标到0
            shiftDown(parent, usedSize);
        }
    }

    // 向下调整算法
    private void shiftDown(int parent, int len){
        int child = parent*2+1;
        while(child < len){  // 注意：len-1为堆数组中最后一个元素的下标
            if(child+1 < len && elem[child] < elem[child+1]){
                child++;
            }

            if(elem[child] > elem[parent]){
                int tmp = elem[child];
                elem[child] = elem[parent];
                elem[parent] = tmp;

                parent = child;
                child = parent*2+1;
            }else{
                break;
            }
        }
    }

    // 插入元素到堆中
    public int offer(int data){
        if(heapIsFull()){
            grow();
        }
        elem[usedSize] = data;
        usedSize++;

        shiftUp(usedSize-1); // 注意：usedSize-1才是data元素的下标

        return data;
    }
    // 向上调整算法
    private void shiftUp(int child){
        int parent = (child-1)/2;
        while(parent >= 0){
            if(elem[child] > elem[parent]){
                int tmp = elem[child];
                elem[child] = elem[parent];
                elem[parent] = tmp;

                child = parent;
                parent = (child-1)/2;
            }else {
                break;
            }
        }
    }
    private boolean heapIsFull(){
        return this.usedSize == this.elem.length;
    }
    private void grow(){
        elem = Arrays.copyOf(this.elem, this.usedSize*2);
    }


    // 删除队头元素
    public int poll(){
        if(heapIsEmpty()){
            return -1;
        }

        int tmp = elem[0];
        elem[0] = elem[usedSize-1];
        elem[usedSize-1] = tmp;
        usedSize--;

        shiftDown(0,usedSize);

        return elem[usedSize];
    }
    private boolean heapIsEmpty(){
        return this.usedSize == 0;
    }


    // 获取队头元素
    public int peek(){
        return elem[0];
    }
}
